findWeb

An example

Some general remark: The algorithms used relay heavily on optimization. Therefore it is not guranteed that the algorithms will find always a errorfree solution (even when you see the errorfree solution).

The Leisepark in Berlin

Part of the package is a data set about portals in the Leisepark in Berlin, Germany (Ingress intel map).

  library("findWeb")
  data(leisepark)
  head(leisepark)

##                                         name             shortname length
## 1 Tombstone Showing A Portal Being Captured    Tombstone Showing …     19
## 2     Grabstätte Familie Schultze und Kramer Grab. Fam. Schultze …     21
## 3             Grabstein Hans-Joachim Wilhelm     Grab. H-J Wilhelm     17
## 4                Ruhestätte Familie Dellscha   Ruhe. Fam. Dellscha     19
## 5                    Hängematte Im Leisepark       Hängematte Im …     15
## 6                    Stolperstein Mendelsohn   Stolper. Mendelsohn     19
##        lat      lon
## 1 52.52955 13.42254
## 2 52.53028 13.42343
## 3 52.52886 13.42308
## 4 52.52963 13.42115
## 5 52.53003 13.42122
## 6 52.53041 13.42391

Step 1: Compute xy portal positions from latitude annd longitude and a web

Convert the latitudes and longitudes to xy-coordinates

  xy <- ll2xy(leisepark$lon, leisepark$lat)
  head(xy)

##             x       y
## [1,] 392992.8 5821108
## [2,] 393054.6 5821188
## [3,] 393027.6 5821031
## [4,] 392898.3 5821119
## [5,] 392903.8 5821163
## [6,] 393087.6 5821201

Next, we will create as target linking structure a fishbone (or herringbone) linking structure.

The fishbone(8) structure consists of nine portals, twentyone links and 19 fields. It was one of the popular linking structures since the EXO5 Controller event in October 2017 since it is simple. And in any case no Softbank Ultra Link is necessary to build it.

Step 2: Create an initial link structure

Then we have to create a starting link structure.

  g0 <- web(g, xy)
  plot(g0)

There are two requirements for a perfect link structure:

• there should be no intersections between links and
• the number of portals inside a field should be larger than in the target linking structure.

The second condition means that for the fishbone(n) the largest field should contain at least n-2 portals. The error value used is the number of link intersections plus number of portals for each field missing to the target link structure.

Step 3: Optimize the link structure by program

The next step is an optimization of the start link structure. The optimizeWeb generates two (at start and end) or even more plots.

Note: the random seed needs to be fixed since the portal positions are generated randomly and the optimization algorithm uses a random search.

  set.seed(1)
  g1 <- optimizeWeb(g0)

In this case the optmization algorithm has found a solution with no errors. It is not guranteed that the program will find a link structure with no errors!

Since the a random search algorithm is used you may repeat the search several times and may become a different solution.

  set.seed(0)
  g11 <- optimizeWeb(g0)

Step 4: Optimize the link structure by hand

However, the solution the program found is not optimal: the outer portals are far away from each other.

  g2 <- swapi(g1)  # swap 42-16
  plot(g2)

What can I do if the program does not find a solution and neither me, too?

The are two parameters you can modify

• increase the number of iterations in the optimization

  set.seed(0)
  g12 <- optimizeWeb(g0, maxit=1000000) # default: 100000

• improve the starting position by rotation for the structure

  g02 <- web(g, xy, rot=32) # default: 16
  plot(g02)

In general the optimization algorithm will honor it if you have more portals available than your target structure requires.

Creating a link plan

As the optimization algorithm the link plan created by the software should only be starting point for a real linking plan.

For a single agent (n=1)

Once you are created a target link structure you need to know which portals to visit and how to link such that you get the maximum number of fields.

We follow the half-plan approach as shown in the video of Michael Hartley: A Fully General Ingress Maxfields Algorithm. The screen shot shows an agent who has a general walking direction east south east (= -22.5 degree or approx -0.0175 radian).

We use the first linking structure which as been created for the Leisepark

  g2 <- linkPlan1(g1)

## [1] -1.996555

  # agent comes from -1.877423 radian or -107 degree or south south west
  plot(g2)

The agent starts at portal blue 9, walks to portal blue 8, … until finally he ends up at portal blue 2, following the pink line.

You may visually check the path and the link plan by (press enter after each agent move)

  getPlan(g2, quiet=TRUE)

The parameter wait determines how the plan is visualiuzed. A negative value (default) means continue after keypress, a positive value continues after wait seconds and a zero does not plot the plan at all.

Now lets head the agent mainly in direction east, coming from the west (= -180 degree = -3.1415 radian)

  g2 <- linkPlan1(g1, dir=-pi)

## [1] -3.141593

  # 2.215663 rad approx. 127 degree, 
  # agent walks comes approxmately from direction north west  
  plot(g2)

And which keys (and softbank ultralinks) are required to build the structure:

 g3 <- linkPlan1(g1)

## [1] -1.996555

 plot(g3)

 getPlan(g3, wait=0)

## 
## Walk 'n link agent 1 (560 m as the crow flies)
##       Portal Link to
##  [1,] "11"   NA     
##  [2,] "33"   "11"   
##  [3,] "24"   "33"   
##  [4,] "42"   "24"   
##  [5,] "32"   "42"   
##  [6,] "7"    "32"   
##  [7,] "20"   "7"    
##  [8,] "37"   "11"   
##  [9,] "37"   "33"   
## [10,] "37"   "24"   
## [11,] "37"   "42"   
## [12,] "37"   "32"   
## [13,] "37"   "7"    
## [14,] "37"   "20"   
## [15,] "6"    "11"   
## [16,] "6"    "37"   
## [17,] "6"    "33"   
## [18,] "6"    "24"   
## [19,] "6"    "42"   
## [20,] "6"    "32"   
## [21,] "6"    "7"    
## [22,] "6"    "20"   
## 
## Required items
##       6 37 20 7 32 42 24 33 11 SBUL
## 1     0  1  2 3  3  3  3  3  3    0
## Total 0  1  2 3  3  3  3  3  3    0

 getPlan(g3, names=leisepark$shortname, wait=0)

## 
## Walk 'n link agent 1 (560 m as the crow flies)
##       Portal                  Link to                
##  [1,] "Grab. Fam. Fritz Jahn" NA                     
##  [2,] "Grab. Fam. Ende"       "Grab. Fam. Fritz Jahn"
##  [3,] "Grab. Fam. Heller"     "Grab. Fam. Ende"      
##  [4,] "Relief"                "Grab. Fam. Heller"    
##  [5,] "Grab. Fam. Ecke"       "Relief"               
##  [6,] "Grab. Ottokar Dohms"   "Grab. Fam. Ecke"      
##  [7,] "Grab. Fam. Kloecke"    "Grab. Ottokar Dohms"  
##  [8,] "Holzmikado"            "Grab. Fam. Fritz Jahn"
##  [9,] "Holzmikado"            "Grab. Fam. Ende"      
## [10,] "Holzmikado"            "Grab. Fam. Heller"    
## [11,] "Holzmikado"            "Relief"               
## [12,] "Holzmikado"            "Grab. Fam. Ecke"      
## [13,] "Holzmikado"            "Grab. Ottokar Dohms"  
## [14,] "Holzmikado"            "Grab. Fam. Kloecke"   
## [15,] "Stolper. Mendelsohn"   "Grab. Fam. Fritz Jahn"
## [16,] "Stolper. Mendelsohn"   "Holzmikado"           
## [17,] "Stolper. Mendelsohn"   "Grab. Fam. Ende"      
## [18,] "Stolper. Mendelsohn"   "Grab. Fam. Heller"    
## [19,] "Stolper. Mendelsohn"   "Relief"               
## [20,] "Stolper. Mendelsohn"   "Grab. Fam. Ecke"      
## [21,] "Stolper. Mendelsohn"   "Grab. Ottokar Dohms"  
## [22,] "Stolper. Mendelsohn"   "Grab. Fam. Kloecke"   
## 
## Required items
##       Stolper. Mendelsohn Holzmikado Grab. Fam. Kloecke
## 1                       0          1                  2
## Total                   0          1                  2
##       Grab. Ottokar Dohms Grab. Fam. Ecke Relief Grab. Fam. Heller
## 1                       3               3      3                 3
## Total                   3               3      3                 3
##       Grab. Fam. Ende Grab. Fam. Fritz Jahn SBUL
## 1                   3                     3    0
## Total               3                     3    0

For more than one agent (n>=1)

For creating a link plan for several agents we follow a different approach. We do it the japanese way starting from the center and building the fields to the outer.

 

From a starting portal (red) we decompose the area in n sectors (here n=3 sectors). Each of the n agents goes to the portals in his sector and links back to all the portals all the agents have visited already.

NOTE: Is is not clear if this approach leads always to the maximum field number!

A cobweb in the Leisepark

As a first step we will create a cobweb with three portals at each leg

g <- cobweb(3)
plot(g)

Then find a solution at the Leisepark

g0 <- web(g, xy)
set.seed(1)
g1 <- optimizeWeb(g0)

plot(g1)

Finally we create a link plan for three agents

g2 <- linkPlanN(g1, agents=3)
plot(g2)

and look for the linking and the keys

getPlan(g2, wait=1) 

## Agent:  1, Portal: 38, SBULs: -0, Link to: 
## Agent:  2, Portal: 38, SBULs: -0, Link to: 
## Agent:  3, Portal: 38, SBULs: -0, Link to: 
## Agent:  1, Portal: 42, SBULs: 0, Link to: 38
## Agent:  3, Portal: 7, SBULs: 0, Link to: 38,42
## Agent:  2, Portal: 34, SBULs: 0, Link to: 42,7,38
## Agent:  1, Portal: 33, SBULs: 0, Link to: 34,42
## Agent:  3, Portal: 20, SBULs: 0, Link to: 34,33,42,7
## Agent:  3, Portal: 39, SBULs: 0, Link to: 33,20
## Agent:  1, Portal: 15, SBULs: 0, Link to: 39,33
## Agent:  2, Portal: 17, SBULs: 0, Link to: 15,39,33,20,34
## 
## Walk 'n link agent 1 (124 m as the crow flies)
##      Portal Link to
## [1,] "38"   NA     
## [2,] "42"   "38"   
## [3,] "33"   "34"   
## [4,] "33"   "42"   
## [5,] "15"   "39"   
## [6,] "15"   "33"   
## 
## Walk 'n link agent 2 (135 m as the crow flies)
##       Portal Link to
##  [1,] "38"   NA     
##  [2,] "34"   "42"   
##  [3,] "34"   "7"    
##  [4,] "34"   "38"   
##  [5,] "17"   "15"   
##  [6,] "17"   "39"   
##  [7,] "17"   "33"   
##  [8,] "17"   "20"   
##  [9,] "17"   "34"   
## 
## Walk 'n link agent 3 (114 m as the crow flies)
##       Portal Link to
##  [1,] "38"   NA     
##  [2,] "7"    "38"   
##  [3,] "7"    "42"   
##  [4,] "20"   "34"   
##  [5,] "20"   "33"   
##  [6,] "20"   "42"   
##  [7,] "20"   "7"    
##  [8,] "39"   "33"   
##  [9,] "39"   "20"   
## 
## Required items
##       17 15 39 34 33 20 38 42 7 SBUL
## 1      0  0  1  1  1  0  1  1 0    0
## 2      0  1  1  1  1  1  1  1 1    0
## 3      0  0  0  1  2  1  1  2 1    0
## Total  0  1  2  3  4  2  3  4 2    0

Of course, a single agent could have done it alone ;)

g4 <- linkPlan1(g1, direction=-pi)

## [1] -3.141593

getPlan(g4, wait=1) 

## Agent:  1, Portal: 15, SBULs: -0, Link to: 
## Agent:  1, Portal: 33, SBULs: 0, Link to: 15
## Agent:  1, Portal: 42, SBULs: 0, Link to: 33
## Agent:  1, Portal: 38, SBULs: 0, Link to: 42
## Agent:  1, Portal: 7, SBULs: 0, Link to: 42,38
## Agent:  1, Portal: 39, SBULs: 0, Link to: 15,33
## Agent:  1, Portal: 20, SBULs: 0, Link to: 33,42,39,7
## Agent:  1, Portal: 34, SBULs: 0, Link to: 33,20,42,7,38
## Agent:  1, Portal: 17, SBULs: 0, Link to: 15,39,33,20,34
## 
## Walk 'n link agent 1 (469 m as the crow flies)
##       Portal Link to
##  [1,] "15"   NA     
##  [2,] "33"   "15"   
##  [3,] "42"   "33"   
##  [4,] "38"   "42"   
##  [5,] "7"    "42"   
##  [6,] "7"    "38"   
##  [7,] "39"   "15"   
##  [8,] "39"   "33"   
##  [9,] "20"   "33"   
## [10,] "20"   "42"   
## [11,] "20"   "39"   
## [12,] "20"   "7"    
## [13,] "34"   "33"   
## [14,] "34"   "20"   
## [15,] "34"   "42"   
## [16,] "34"   "7"    
## [17,] "34"   "38"   
## [18,] "17"   "15"   
## [19,] "17"   "39"   
## [20,] "17"   "33"   
## [21,] "17"   "20"   
## [22,] "17"   "34"   
## 
## Required items
##       17 15 39 34 33 20 38 42 7 SBUL
## 1      0  3  2  1  5  2  2  4 2    0
## Total  0  3  2  1  5  2  2  4 2    0

Helpful informations

Plotting

The plot command offers additional parameters which are set on TRUE by default.

plot(g4, blue=FALSE) # do not plot the blue numbers

plot(g4, black=FALSE) # do not plot the black numbers

plot(g4, links=FALSE) # do not plot the links

plot(g4, pathes=FALSE) # do not plot the agent pathes

Using the forward pipe operator

To simplify the typing you may use the forward pipe operator %>% of the library magrittr. Instead of writing

g0 <- fishbone(8)
g1 <- web(g0, xy)
g2 <- optimizeWeb(g1)
g3 <- linkPlan1(g2)
plot(g3, blue=FALSE)

you may use

library("magrittr") # for %>% operator
fishbone(8) %>% web(xy) %>% optimizeWeb() %>% linkPlan1() %>% plot(blue=FALSE)

## [1] -1.842887

Or alternatively

g <- fishbone(8) %>% web(xy) %>% optimizeWeb() %>% linkPlan1()
plot(g, blue=FALSE)

Thanks

Finally, a thanks to Stefan Dirsch for testing the R package, Michael Hartley for his videos and the authors of R package FNN: Fast Nearest Neighbor Search Algorithms and Applications ;)

Enjoy planing and linking, agents!